package m202403.d29;

import java.util.Arrays;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/3/29 20:05
 */
public class Q912 {
    public int[] sortArray(int[] nums) {
        return bubbleSorting(nums);
    }

    //冒泡排序
    private int[] bubbleSorting(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean flag = false;
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
        return nums;
    }

    //插入排序
    private int[] insertSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }
            }
        }
        return nums;
    }

    //选择排序
    private int[] selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
        return nums;
    }


    public static void main(String[] args) {
//        new Q912().quickSort(new int[]{5, 1, 1, 2, 0, 0});
        System.out.println(4 << 10);
    }

    //归并排序
    //[5,2,3,1]
    private int[] mergeSort(int[] nums) {
        split(nums, 0, nums.length);
        return nums;
    }

    private void split(int[] nums, int start, int end) {
        if (start + 1 == end) {
            return;
        }
        int mid = start + (end - start) / 2;
        split(nums, start, mid);
        split(nums, mid, end);
        merge(nums, start, mid, end);
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int[] rs = new int[end - start];
        int i = start, j = mid, k = 0;
        for (; i < mid && j < end; k++) {
            if (nums[i] < nums[j]) {
                rs[k] = nums[i];
                i++;
            } else {
                rs[k] = nums[j];
                j++;
            }
        }
        if (mid - i > 0) {
            System.arraycopy(nums, i, rs, k, mid - i);
        }
        if (end - j > 0) {
            System.arraycopy(nums, j, rs, k, end - j);
        }
        System.arraycopy(rs, 0, nums, start, rs.length);
    }


    private int[] quickSort(int[] nums) {
        qSplit(nums, 0, nums.length);
        return nums;
    }

    private void qSplit(int[] nums, int start, int end) {
        if (end - start <= 1) {
            return;
        }
        int mid = partition(nums, start, end);
        qSplit(nums, 0, mid);
        qSplit(nums, mid + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int flagValue = nums[end - 1];
        int i = start, j = end - 1;
        int flag = flagValue;
        for (; i < j; ) {
            if (nums[i] >= flagValue) {
                int temp = nums[start];
                nums[start] = nums[j];
                nums[j] = temp;
                j--;
            } else {
                i++;
            }
            if (nums[i] == flagValue) {
                flag = i;
            }
        }

        return flag;
//        int[] temp = new int[end - start];
//        int i = start, j = 0, k = temp.length - 1;
//        for (; i < end; i++) {
//            if (nums[i] < flagValue) {
//                temp[j] = nums[i];
//                j++;
//            } else {
//                temp[k] = nums[i];
//                k--;
//            }
//        }
//        System.arraycopy(temp, 0, nums, start, temp.length);
//        return start+j;
    }

//    private int getFlag(int[] nums, int start, int end) {
//        int s = nums[start];
//        int e = nums[end - 1];
//        int m = nums[start + (end - start) / 2];
//        int min = Math.min(s, Math.min(e, m));
//        int max = Math.max(s, Math.max(e, m));
//        if (s >= min && s <= max) {
//            return start;
//        } else if (e >= min && e <= max) {
//            return end - 1;
//        } else {
//            return start + (end - start) / 2;
//        }
//    }
}
